def bubble_sort_v1(array=[]):
    for i in range(len(array) - 1):
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
        print('-----------' + str(i))


def bubble_sort_v2(array=[]):
    for i in range(len(array) - 1):
        is_sorted = True
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
                is_sorted = False
        if is_sorted:
            print('-----------' + str(i))
            break


def bubble_sort_v3(array=[]):
    last_exchange_index = 0
    sort_border = len(array) - 1
    for i in range(len(array) - 1):
        print('-----------' + str(i))
        is_sorted = True
        for j in range(sort_border):
            if array[j] > array[j + 1]:
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
                is_sorted = False
                last_exchange_index = j
        sort_border = last_exchange_index
        if is_sorted:
            print('-----------' + str(i))
            break


def cock_tail_sort(array=[]):
    for i in range(len(array) // 2):
        is_sorted = True
        # 基数轮，从左向右比较和交换
        for j in range(i, len(array) - i - 1):
            if array[j] > array[j + 1]:
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
                is_sorted = False
        print('------1-----' + str(i))
        print(array)
        if is_sorted:
            break
        is_sorted = True
        for j in range(len(array) - i - 1, i, -1):
            if array[j] < array[j - 1]:
                temp = array[j]
                array[j] = array[j - 1]
                array[j - 1] = temp
                is_sorted = False
        print('-------2----' + str(i))
        print(array)
        if is_sorted:
            break


def quick_sort(start_index, end_index, array=[]):
    # 递归结束条件:start_index大于等于end_index的时候
    if start_index >= end_index:
        return
    # 得到基准元素位置
    pivot_index = partition_v1(start_index, end_index, array)
    # 根据基准元素，分成两部分递归排序
    quick_sort(start_index, pivot_index - 1, array)
    quick_sort(pivot_index + 1, end_index, array)


def partition_v1(start_index, end_index, array=[]):
    pivot = array[start_index]
    print(pivot)
    print(array)
    left = start_index
    right = end_index
    while left != right:
        while left < right and array[right] > pivot:
            right -= 1
        while left < right and array[left] <= pivot:
            left += 1
        if left < right:
            p = array[left]
            array[left] = array[right]
            array[right] = p
    array[start_index] = array[left]
    array[left] = pivot
    return left


def quick_sort2(start_index, end_index, array=[]):
    if start_index >= end_index:
        return
    pivot_index = partition_v2(start_index, end_index, array)
    quick_sort2(start_index, pivot_index - 1, array)
    quick_sort2(pivot_index + 1, end_index, array)


def partition_v2(start_index, end_index, array=[]):
    pivot = array[start_index]
    mark = start_index
    print(pivot)
    for i in range(start_index + 1, end_index + 1):
        if array[i] < pivot:
            mark += 1
            temp = array[mark]
            array[mark] = array[i]
            array[i] = temp
    array[start_index] = array[mark]
    array[mark] = pivot
    print(array)
    return mark


def count_sort(array=[]):
    # 求最大值
    max_value = array[0]
    for i in range(len(array)):
        if array[i] > max_value:
            max_value = array[i]
    # 根据数列最大值，确定统计数组的长度
    count_array = [0] * (max_value + 1)
    # 遍历数列，填充统计数组
    for i in range(0, len(array)):
        count_array[array[i]] += 1
    # 遍历统计数组，输出结果
    sort_array = []
    for i in range(0, len(count_array)):
        for j in range(0, count_array[i]):
            sort_array.append(i)
    return sort_array


if __name__ == '__main__':
    # my_array1 = list([3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11])
    # bubble_sort_v1(my_array1)
    # print(my_array1)
    #
    # my_array2 = list([3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11])
    # bubble_sort_v2(my_array2)
    # print(my_array2)
    #
    # my_array3 = list([3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11])
    # bubble_sort_v3(my_array3)
    # print(my_array3)

    # my_array11 = list([2, 4, 3, 1, 5, 6, 7, 8])
    # bubble_sort_v1(my_array11)
    # print(my_array11)
    #
    # my_array22 = list([2, 4, 3, 1, 5, 6, 7, 8])
    # bubble_sort_v2(my_array22)
    # print(my_array22)
    #
    # my_array33 = list([2, 4, 3, 1, 5, 6, 7, 8])
    # bubble_sort_v3(my_array33)
    # print(my_array33)

    # my_array34 = list([2, 3, 4, 5, 6, 7, 8, 1])
    # bubble_sort_v3(my_array34)
    # print(my_array34)

    # my_cock_array = list([3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11])
    # cock_tail_sort(my_cock_array)
    # print(my_cock_array)
    # my_quick_array = list([4, 7, 6, 5, 3, 2, 8, 1])
    # quick_sort(0, len(my_quick_array) - 1, my_quick_array)
    # print(my_quick_array)

    # my_quick_array2 = list([4, 7, 6, 5, 3, 2, 8, 1])
    # quick_sort2(0, len(my_quick_array2) - 1, my_quick_array2)
    # print(my_quick_array2)
    my_array = list([4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10])
    print(count_sort(my_array))
